package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T26 {
    public static void main(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(new T26().removeDuplicates(nums));
        System.out.println(Arrays.toString(nums));
    }

    public int removeDuplicates(int[] nums) {
        int l = 0;
        while (l < nums.length - 1) {

            if (nums[l] == nums[l + 1] || (l > 0 && nums[l] < nums[l - 1])) {
                int more = Math.max(nums[l], l > 0 ? nums[l - 1] : Integer.MIN_VALUE);
                int next = findNextMore(nums, l, more);
                if (next == -1) {
                    return l;
                }
                swap(nums, (l > 0 && nums[l] < nums[l - 1]) ? l : l + 1, next);
                l++;
            } else {
                l++;
            }

        }
        return l;
    }

    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

    private int findNextMore(int[] nums, int start, int val) {
        int end = nums.length;

        while (start + 1 < end) {
            int mid = ((start - end) / 2) + end;
            int cur = nums[mid];
            if (cur > val) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return nums[end] > val ? end : -1;
    }
}
